This invention relates to control data generators for sort processors for sorting a great number of data according to a specified order.
A conventional control data generator for a sort processor such as shown in FIG. 1 of the Proceedings of the Japanese Electronic Communications Society, J66-D, March 1983, p 333, is shown in FIG. 6. The control data generator includes four sort processors 1-4, four memories 5-8 each corresponding to each sort processor, and an indicator 9 for the length (L) of data set by the sort processor. The i-th sort processor from left is provided with a memory which has a capacity of 2.sup.i-1 L.
In operation, the data to be sorted is sequentially input into the sort processor 1. The sort processor 1 stores one of the input data in the memory 5 and compares it with the next input data. For sorting in descending order, the sort processor 1 first outputs the greater one between the two data and then the smaller one to the next sort processor 2. This operation is repeated in the sort processor 1.
The sort processor 2 stores the descending order 2-data set in the memory 6, in which the two data are sorted in descending order, and merges it with the next input descending order 2-data set to output a descending order 4-data set to the sort processor 3. This operation is repeated in the sort processor 2.
Generally, the i-th sort processor merges the descending order 2.sup.i-1 -data set sent from the (i-1)th sort processor to output a descending order 2.sup.i -data set to the (i+1)th sort processor. This operation is repeated in the i-th sort processor. Thus, when N (=2.sup.n) data are input, the n-th sort processor outputs a descending order N-data set sorted.
The above operation, however, is possible only if the length (X) of data to be sorted is either equal to or less than the length (L) of data set by the sort processor.
In accordance with the Proceedings of the 5th international Workshop on Database Machines, October 1986, p 144, even if the input data length (X) is greater than the set data length (L), it is possible to sort a great number of such data by dynamically switching the first sort processor 1 between the MRG mode in which merge is carried out as described above and the NM mode in which no merging operation is performed, with the input data directly transmitted to the sort processor 2, depending on the input data length (X) to thereby use the memories 5-8 more efficiently.
For example, let X=1.1 L in the descending order sorting. Since the capacity of the memory 8 for the sort processor 4 is 8 L, it is possible to store seven data in the memory as follows: EQU 8 L/X=8L/1.1L=7.27. . .=7 (integer part).
The sort processor 3 outputs a descending order 7-data set having a data length of 7 to the sort processor 4 and repeats this operation. The sort processor 2 repeats outputting a descending order 3-data set and a descending order 4-data set to the sort processor 3. The sort processor 1 repeats outputting descending order 1-data, 2-data, 2-data, and 2-data sets to the sort processor 2. These operations are shown in FIG. 5.
In FIG. 5, th data 17-30 to be input to the sort processor are shown in the inputting order. Symbols NM 31 and MRG 32-37 indicate that the sort processor 1 is brought into control in the NM mode for data 17 and 24 and into the MRG mode for data 18, 25, etc., respectively. The value (n) of a descending order n-data set to be generated by the sort processor 3 is shown at 10. Similarly, the values (n) of descending order n-data sets to be generated by the sort processor 2 are shown at 11 and 12. The values (n) of descending order n-data sets to be generated periodically by the sort processor 1 are shown at 13-16. The sort processors 1, 2, and 3 in FIG. 6 are represented by P1, P2, and P3.
In this way, the third sort processor 3 always outputs a descending order 7-data set to the fourth sort processor 4. Thus, with the control data generator for a sort processor of FIG. 6, it is possible to sort 14 data under the above conditions. However, the procedure of generating the control data is so complex that there are no ways but by programming. As a result, the sorting capability has been impaired.